/*
 * @Author: du.j
 * @Date: 2020-05-06 10:28:33
 * @LastEditors: du.j
 * @LastEditTime: 2020-06-30 11:07:17
 * @Description: 冒泡排序  O(n²)
 *
 * 思想
 *
 * 冒泡排序只会操作相邻的两个数据。
 * 每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。
 * 一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
 *
 * 特点
 * 优点：排序算法的基础，简单实用易于理解。
 * 缺点：比较次数多，效率较低。
 */

/**
 * 1、冒泡排序（未优化）
 * @param {Array} arr
 */
const bubbleSort1 = (arr) => {
  console.time("改进前冒泡排序耗时");
  const length = arr.length;
  if (length <= 1) return;
  // i < length - 1 是因为外层只需要 length-1 次就排好了，第 length 次比较是多余的。
  for (let i = 0; i < length - 1; i++) {
    // j < length - i - 1 是因为内层的 length-i-1 到 length-1 的位置已经排好了，不需要再比较一次。
    for (let j = 0; j < length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  console.log("改进前 arr :", arr);
  console.timeEnd("改进前冒泡排序耗时");
};

/**
 * 2、冒泡排序（已优化）
 * @param {Array} arr
 */
const bubbleSort = (arr) => {
  console.time("改进后冒泡排序耗时");
  const length = arr.length;
  if (length <= 1) return;
  // i < length - 1 是因为外层只需要 length-1 次就排好了，第 length 次比较是多余的。
  for (let i = 0; i < length - 1; i++) {
    let hasChange = false; // 提前退出冒泡循环的标志位
    // j < length - i - 1 是因为内层的 length-i-1 到 length-1 的位置已经排好了，不需要再比较一次。
    for (let j = 0; j < length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        hasChange = true; // 表示有数据交换
      }
    }

    if (!hasChange) break; // 如果 false 说明所有元素已经到位，没有数据交换，提前退出
  }
  console.log("改进后 arr :", arr);
  console.timeEnd("改进后冒泡排序耗时");
};
